Теорема Шура (теория Рамсея)

Теорема Шура — утверждение в теории Рамсея о том, что при любой раскраске натуральных чисел в конечное число цветов найдётся одноцветное решение уравнения $x+y=z$. Названа в честь её автора, Исая Шура.

История возникновения

Теорема Шура возникла как инструмент для доказательства одного утверждения, тривиально следовавшего бы из отрицания тогда ещё не доказанной Великой теоремы Ферма, а именно — ответа на вопрос о разрешимости её уравнения в кольце вычетов по достаточно большому простому модулю: для всякого ли $n\geq 3$ при простых $p>p_{0}=p_{0}(n)$ уравнение

$x^{n}+y^{n}\equiv z^{n}{\pmod {p}}$

имеет ненулевые решения?

Такие уравнения (и подобные им) рассматривались ещё Гульельмо Либри в 1832 году, но только в 1909 Леонард Юджин Диксон получил первый общий результат по этой теме — показал правильность этого утверждения для всех простых $n$.

Диксон действовал теоретико-числовыми методами, но Шур в 1917 году применил к проблеме комбинаторный подход, рассмотрев разбиение кольца по простому модулю на классы вычетов, соответствующие разным значениям дискретного логарифма того или иного вычета по модулю $n$ (иначе говоря, на смежные классы мультипликативных подгрупп). В этом случае умножением всех переменных на первообразный корень можно «перебрасывать» решения любого линейного уравнения из одного класса в другой (если до умножения все переменные находились в одном классе, то и после такой «переброски» будет так же). Благодаря этому утверждение рамсеевского типа (о существовании лишь элемента разбиения, но не о свойствах каждого конкретного множества) относительно линейных уравнений легко превращается в теоретико-числовое утверждение (о свойствах множества), поскольку существование конфигурации в одном элементе разбиения влечёт её существование во всех других.

Формулировка

Если ${\mathbb {N} }={\mathcal {N}}_{1}\cup {\mathcal {N}}_{2}\cup \dots \cup {\mathcal {N}}_{k}$, то $\exists i,x,y:\ \left\lbrace {x,y,x+y}\right\rbrace \subset {\mathcal {N}}_{i}$

Как и многие утверждения из теории Рамсея, теорема Шура допускает также конечную формулировку. Это означает, что при фиксированном $k$ минимальные из подходящих под условие $x,y$ не могут быть сколь угодно большими.

Конечный вариант Для всякого $k$ существует $S=S(k)$ такое, что если $\{1,2,\dots ,S\}={\mathcal {N}}_{1}\cup {\mathcal {N}}_{2}\cup \dots \cup {\mathcal {N}}_{k}$, то $\exists i,x,y:\ \left\lbrace {x,y,x+y}\right\rbrace \subset {\mathcal {N}}_{i}$

Доказательство

Теорему Шура принято доказывать в конечной формулировке рассмотрением $S=R(3,\dots ,3)$, то есть числа Рамсея для 3-клик (треугольников) при раскраске в $k$ цветов. Если $c(n)$ означает цвет числа $n$ в некоторой фиксированной раскраске $\{1,\dots ,S\}$, то при раскраске рёбер полного графа $K_{S}$ таким образом, что ${\overline {c}}(i,j)=c(|i-j|)$, существование одноцветного треугольника влечёт существование нужного одноцветного решения в разбиении $\{1,\dots ,S\}$

На момент первой публикации теоремы Шура теорема Рамсея ещё не была известна, но Шур проводил для разностей чисел, принадлежащих одному из классов разбиения, рассуждения, полностью аналогичные проводимым при общем доказательстве теории Рамсея.

Такое доказательство даёт оценку $S<e\cdot (n!)$. В приложении к вопросу о разрешимости уравнения $x^{n}+y^{n}\equiv z^{n}{\pmod {p}}$ для рассматривавшихся ранее значений $n$ она оказалась хуже полученной Либри (он показал, что при простых $n$ достаточно условия $p>n^{4}$).

Связь с другими теоремами

Теорема Шура очень похожа на теорему ван дер Вардена для прогрессий длины 3 (потому что такая прогрессия — суть решение уравнения $x+y=2z$), однако, в отличие от неё, не допускает аддитивно-комбинаторного обобщения (каковым для теоремы ван дер Вардена является теорема Рота), поскольку само по себе свободное от сумм множество может быть достаточно плотным (например, множество всех нечётных чисел).

См. также

• Теорема Фолкмана

Литература

• Par Mr. G. Libri de Florence. Mémoire sur la théorie des nombres. (фр.) // Journal für die reine und angewandte Mathematik. — 1832. — Vol. 9, livr. 2. — P. 261-276.
• Mr. L. E. Dickson. On the congruence $x^{n}+y^{n}+z^{n}\equiv 0{\pmod {p}}$ (англ.) // Journal für die reine und angewandte Mathematik. — 1909. — Vol. 135. — P. 134-141.
• I. Schur. Über die Kongruenz $x^{m}+y^{m}\equiv z^{m}{\pmod {p}}$ (нем.) // Jahresbericht der Deutschen Mathematiker-Vereinigung. — 1917. — Bd. 25. — S. 114-117.